//翻转对
class Solution {
public:
    vector<long long >tmp;
    int res=0;
    int reversePairs(vector<int>& nums) 
    {
        int n=nums.size();
        tmp.resize(n);
        mergeSort(nums,0,n-1);
        return res;
    }
    void mergeSort(vector<int>& nums,int l,int r)
    {
        if(l>=r) return;
        int mid=(l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);

        int i=0;
        int cur1=l,cur2=mid+1;
        while(cur1<=mid && cur2<=r)
        {
            while(cur2<=r && (long long)nums[cur1]<=(long long)2*nums[cur2]) cur2++;
            if(cur2>r) break;
            else
            {
                res+=r-cur2+1;
                cur1++;
            }
        }
        cur1=l,cur2=mid+1;
        while(cur1<=mid && cur2<=r)
        {
            //该部分的逻辑 只有nums[cur1]>2*nums[cur2]时
            //才会正确更新Res
            //但有情况是
            //2*nums[cur2]> nums[cur1] > 2*nums[cur2+1]
            //这种情况没有考虑 直接让cur1++ 导致结果出错
            // if(nums[cur1]>nums[cur2])
            // {
            //     if(nums[cur1] > 2*nums[cur2])
            //     {
            //         res+=(r-cur2+1);
            //     }
            //     tmp[i++]=nums[cur1++];
            // }
            if(nums[cur1]>nums[cur2]) tmp[i++]=nums[cur1++];
            else tmp[i++]=nums[cur2++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=r) tmp[i++]=nums[cur2++];
        for(int i=l,j=0;i<=r;i++,j++)
        {
            nums[i]=tmp[j];
        }
    }
};